home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / man / lib.fmt / c / List.man < prev    next >
Encoding:
Text File  |  1989-12-14  |  10.4 KB  |  267 lines
  1.  
  2.  
  3.  
  4. List                  C Library Procedures                   List
  5.  
  6.  
  7.  
  8. _________________________________________________________________
  9.  
  10. NNAAMMEE
  11.      List - overview of circular linked list routines.
  12.  
  13. SSYYNNOOPPSSIISS
  14.      ##iinncclluuddee <<lliisstt..hh>>
  15.  
  16.      LLiisstt__IInniitt(_h_e_a_d_e_r_P_t_r)
  17.      LLiisstt__IInniittEElleemmeenntt(_i_t_e_m_P_t_r)
  18.      LLiisstt__IInnsseerrtt(_i_t_e_m_P_t_r, _d_e_s_t_P_t_r)
  19.      LLiisstt__LLiissttIInnsseerrtt(_h_e_a_d_e_r_P_t_r, _d_e_s_t_P_t_r)
  20.      LLiisstt__RReemmoovvee(_i_t_e_m_P_t_r)
  21.      LLiisstt__MMoovvee(_i_t_e_m_P_t_r, _d_e_s_t_P_t_r)
  22.  
  23.      LLIISSTT__AAFFTTEERR(_i_t_e_m_P_t_r)
  24.      LLIISSTT__BBEEFFOORREE(_i_t_e_m_P_t_r)
  25.      LLIISSTT__AATTFFRROONNTT(_h_e_a_d_e_r_P_t_r)
  26.      LLIISSTT__AATTRREEAARR(_h_e_a_d_e_r_P_t_r)
  27.  
  28.      LLIISSTT__FFOORRAALLLL(_h_e_a_d_e_r_P_t_r, _i_t_e_m_P_t_r)
  29.  
  30.      LLiisstt__IIssEEmmppttyy((_h_e_a_d_e_r_P_t_r))
  31.      LLiisstt__IIssAAttEEnndd(_h_e_a_d_e_r_P_t_r, _i_t_e_m_P_t_r)
  32.      LLiisstt__FFiirrsstt((_h_e_a_d_e_r_P_t_r))
  33.      LLiisstt__LLaasstt((_h_e_a_d_e_r_P_t_r))
  34.      LLiisstt__PPrreevv((_i_t_e_m_P_t_r))
  35.      LLiisstt__NNeexxtt((_i_t_e_m_P_t_r))
  36.  
  37. AARRGGUUMMEENNTTSS
  38.      List_Links   *_h_e_a_d_e_r_P_t_r   (in)      Pointer to the header of
  39.                                          a list.
  40.  
  41.      List_Links   *_i_t_e_m_P_t_r     (in)      Pointer to a member of a
  42.                                          list    (possibly    the
  43.                                          header).
  44.  
  45.      List_Links   *_d_e_s_t_P_t_r     (in)      Pointer  to  the  member
  46.                                          after which to insert or
  47.                                          move another member.
  48.  
  49. _________________________________________________________________
  50.  
  51.  
  52. IINNTTRROODDUUCCTTIIOONN
  53.      The LLiisstt__ routines define the  ``list''  abstraction,  which
  54.      enables  one  to  link  together  arbitrary data structures.
  55.      Lists are doubly-linked and circular.   A  list  contains  a
  56.      header followed by its real members, if any.  (An empty list
  57.      therefore consists of a single element, the  header,   whose
  58.      _n_e_x_t_P_t_r  and _p_r_e_v_P_t_r fields point to itself).  To refer to a
  59.      list as a whole, the user keeps a  pointer  to  the  header;
  60.      that  header  is initialized by a call to LLiisstt__IInniitt(()), which
  61.      creates an empty  list  given  a  pointer  to  a  List_Links
  62.  
  63.  
  64.  
  65. Sprite v.1.0       Printed:  December 14, 1989                  1
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72. List                  C Library Procedures                   List
  73.  
  74.  
  75.  
  76.      structure (described below).
  77.  
  78.      The links are contained in a  two-element  structure  called
  79.      List_Links.   A list joins List_Links records (that is, each
  80.      List_Links structure points to other List_Links structures),
  81.      but  if  the  List_Links  is the first field within a larger
  82.      structure, then the larger structures are effectively linked
  83.      together as shown in Figure 1.
  84.  
  85.      A typical structure might be something like:
  86.  
  87.           typedef struct {
  88.                       List_Links links;
  89.                       char ch;
  90.                       int flags;
  91.           } EditChar;
  92.  
  93.      It is possible to link structures through List_Links  fields
  94.      that  are  not at the beginning of the larger structure, but
  95.      it is  then  necessary  to  perform  an  additional  pointer
  96.      indirection  to  find the beginning of the larger structure,
  97.      given a pointer to some point within it.  The easiest way to
  98.      do  this is to define a structure that contains a List_Links
  99.      field and a pointer to the larger structure, such as:
  100.           typedef struct {
  101.                       List_Links links;
  102.                       LargeStruct *structPtr;
  103.           } LargeStructLink;
  104.  
  105.      By including a ``LargeStructLink'' within a  ``LargeStruct''
  106.      and  setting  the  structPtr field of the LargeStructLink to
  107.      point to the LargeStruct itself, LargeStruct structures  may
  108.      be linked together in a list that is contained in the middle
  109.      of the structure rather than the beginning.
  110.  
  111.  
  112. UUSSAAGGEE
  113.      After a list has been initialized by calling LLiisstt__IInniitt, ele-
  114.      ments  may  be  inserted, deleted, or moved within the list.
  115.      Before an element is inserted in a list for the  first  time
  116.      it    must   be   initialized   by   calling   the   routine
  117.      LLiisstt__IInniittEElleemmeenntt.  To insert a  List_Links  element  into  a
  118.      list,  LLiisstt__IInnsseerrtt  is called with two arguments.  The first
  119.      argument is a pointer to the structure to be inserted into a
  120.      list,  and  the  second  argument  is  a pointer to the list
  121.      member after which it is to  be  inserted.   Typically,  the
  122.      following  macros  are used to select the insertion point or
  123.      the destination of a LLiisstt__MMoovvee:
  124.  
  125.  
  126.  
  127.           o+ LLIISSTT__BBEEFFOORREE(_i_t_e_m_P_t_r)        Insert the element before
  128.  
  129.  
  130.  
  131. Sprite v.1.0       Printed:  December 14, 1989                  2
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138. List                  C Library Procedures                   List
  139.  
  140.  
  141.  
  142.                                         *_i_t_e_m_P_t_r.
  143.  
  144.           o+ LLIISSTT__AAFFTTEERR(_i_t_e_m_P_t_r)         Insert the element  after
  145.                                         *_i_t_e_m_P_t_r.
  146.  
  147.           o+ LLIISSTT__AATTFFRROONNTT(_h_e_a_d_e_r_P_t_r)     Insert the element at the
  148.                                         front of the list.
  149.  
  150.           o+ LLIISSTT__AATTRREEAARR(_h_e_a_d_e_r_P_t_r)      Insert the element at the
  151.                                         end of the list.
  152.  
  153.      To insert a list into  another  list,  call  LLiisstt__LLiissttIInnsseerrtt  |
  154.      with  the header of the list to be inserted and a pointer to  |
  155.      the member of the second list after which the first list  is  |
  156.      to  be  inserted.  After calling LLiisstt__LLiissttIInnsseerrtt, the header  |
  157.      of the first list is no longer valid and may be destroyed.
  158.  
  159.      To remove a structure from a list, call LLiisstt__RReemmoovvee  with  a
  160.      pointer to the structure to be removed. To move a structure,
  161.      call LLiisstt__MMoovvee with two arguments: a pointer to  the  struc-
  162.      ture to be moved, and a pointer to the structure after which
  163.      it is to be placed.  LLiisstt__MMoovvee(_i_t_e_m_P_t_r, _d_e_s_t_P_t_r)  is  there-
  164.      fore   equivalent   to   LLiisstt__RReemmoovvee(_i_t_e_m_P_t_r)   followed  by
  165.      LLiisstt__IInnsseerrtt(_i_t_e_m_P_t_r, _d_e_s_t_P_t_r).
  166.  
  167.  
  168. AADDDDIITTIIOONNAALL UUTTIILLIITTIIEESS
  169.      Several other macros are available for the  manipulation  of
  170.      List_Links.  LLIISSTT__FFOORRAALLLL(_h_e_a_d_e_r_P_t_r, _i_t_e_m_P_t_r) is used to step
  171.      through each element in the list pointed  to  by  headerPtr,
  172.      setting   itemPtr   to   point  to  each  element  in  turn.
  173.      LLIISSTT__FFOORRAALLLL is  used  typically  by  casting  _i_t_e_m_P_t_r  as  a
  174.      pointer to the entire structure, as in:
  175.           List_Links *headerPtr;   /* pointer to head of existing list */
  176.           List_Links *itemPtr;     /* place-holder during loop */
  177.           EditChar   *charPtr;     /* pointer to entire EditChar structure */
  178.  
  179.           LIST_FORALL(headerPtr, itemPtr) {
  180.                charPtr = (EditChar *) itemPtr;
  181.                /* operations using charPtr */
  182.           }
  183.  
  184.      The  following  macros  may  be  useful  to  those  who  use
  185.      List_Links  at  a  ``lower''  level  than looping through an
  186.      entire list:
  187.  
  188.           o+ LLiisstt__IIssEEmmppttyy(_h_e_a_d_e_r_P_t_r)     returns TRUE if _h_e_a_d_e_r_P_t_r
  189.                                         points to an empty list.
  190.  
  191.           o+ LLiisstt__IIssAAttEEnndd(_h_e_a_d_e_r_P_t_r, _i_t_e_m_P_t_r)
  192.                                         returns TRUE  if  _i_t_e_m_P_t_r
  193.                                         is  past  the  end of the
  194.  
  195.  
  196.  
  197. Sprite v.1.0       Printed:  December 14, 1989                  3
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204. List                  C Library Procedures                   List
  205.  
  206.  
  207.  
  208.                                         list; i.e., it points  to
  209.                                         the header.
  210.  
  211.           o+ LLiisstt__FFiirrsstt(_h_e_a_d_e_r_P_t_r)
  212.  
  213.           o+ LLiisstt__LLaasstt(_h_e_a_d_e_r_P_t_r)        LLiisstt__FFiirrsstt  returns   the
  214.                                         first  member  in a list,
  215.                                         and LLiisstt__LLaasstt returns the
  216.                                         last member.  If the list
  217.                                         is empty, the  header  is
  218.                                         considered   to   be  the
  219.                                         first and last member.
  220.  
  221.           o+ LLiisstt__PPrreevv(_i_t_e_m_P_t_r)          returns a pointer to  the
  222.                                         member    preceding   the
  223.                                         given member in its list.
  224.                                         Note:    if   the   given
  225.                                         member is the first  ele-
  226.                                         ment    of    the   list,
  227.                                         LLiisstt__PPrreevv will return the
  228.                                         list header.
  229.  
  230.           o+ LLiisstt__NNeexxtt(_i_t_e_m_P_t_r)          returns the  next  member
  231.                                         of  the  list.  Note:  if
  232.                                         the given member  is  the
  233.                                         last element of the list,
  234.                                         LLiisstt__NNeexxtt will return the
  235.                                         list header.
  236.  
  237. KKEEYYWWOORRDDSS
  238.      list, linked, circular, List_Links, data structures
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263. Sprite v.1.0       Printed:  December 14, 1989                  4
  264.  
  265.  
  266.  
  267.